#include <iostream>
#include <vector>

using namespace std;
// 88.合并两个有序数组
// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。(不用开辟新的空间)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1, j = n-1;
        for(int k = m+n-1; k >= 0; k--) {   // 从后往前，直接考虑nums1每个位置放什么
            // 什么时候要nums1[i]？或者j出界了，或者i,j都没出界，要大的
            if(j < 0 || (i >= 0 && nums1[i] >= nums2[j])) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
        }
    }
};

void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {
    vector<int> nums1 = {1, 3, 5, 7};
    int m = nums1.size();

    vector<int> nums2 = {2, 4, 6};
    int n = nums2.size();

    for( int i = 0 ; i < nums2.size() ; i ++ )
        nums1.push_back(0);

    Solution().merge(nums1, m, nums2, n);
    print_vec(nums1);
    return 0;
}
